package array

// 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
// 在「杨辉三角」中，每个数是它左上方和右上方的数的和

func Generate(numRows int) [][]int {

	res := make([][]int, numRows)

	// 第零行和第一行所有值都为1
	if numRows == 1 {
		res[0] = []int{1}
		return res
	} else {
		res[0] = []int{1}
		res[1] = []int{1, 1}
	}

	// 杨辉三角的每个位置的值（除了一二列和边上的值） = 上一行[index-1]+上一行[index]
	// 边上的值为1
	for i := 2; i < numRows; i++ {
		rowLen := i + 1
		res[i] = make([]int, rowLen)
		res[i][0] = 1
		res[i][rowLen-1] = 1
		for j := 1; j < rowLen-1; j++ {
			res[i][j] = res[i-1][j-1] + res[i-1][j]
		}
	}

	return res
}
